home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graph / speed.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.2 KB  |  183 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/ugraph.h>
  3. #include <LEDA/graph_alg.h>
  4.  
  5.  
  6. main(int argc, char** argv)
  7. {
  8.   int n = read_int("|V| = ");
  9.   int m = read_int("|E| = ");
  10.  
  11.   init_random(n*m);
  12.  
  13.   float T = used_time();
  14.  
  15.   cout << "build graph          " << flush;
  16.   GRAPH<string,int> G1;
  17.   random_graph(G1,n,m);
  18.   cout << string("%6.2f sec\n",used_time(T));
  19.  
  20.   cout << "build ugraph         " << flush;
  21.   UGRAPH<string,int> U = G1;
  22.   cout << string("%6.2f sec\n",used_time(T));
  23.  
  24.   cout << "build bi-graph       " << flush;
  25.   GRAPH<string,int> G2;
  26.   list<node> A;
  27.   list<node> B;
  28.   random_bigraph(G2,n/2,n/2,m,A,B);
  29.   cout << string("%6.2f sec\n",used_time(T));
  30.  
  31.   node s = G1.first_node();
  32.   node t = G1.last_node();
  33.  
  34.   cout << "node/edge arrays     " << flush;
  35.  
  36.   edge_array<int>     cost1(G1);
  37.   edge_array<double>  cost2(G1);
  38.   node_array<int>     dist1(G1);
  39.   node_array<double>  dist2(G1);
  40.   node_array<edge>    pred(G1);
  41.   edge_array<int>     flow1(G1);
  42.   edge_array<double>  flow2(G1);
  43.  
  44.   node_array<int>  ord(G1);
  45.   node_array<int>  compnum(G1);
  46.   node_array<int>  reached(G1,false);
  47.   node_array<int>  dfs_num(G1);
  48.   node_array<int>  comp_num(G1);
  49.   node_array<int>  layer(G1,-1);
  50.  
  51.   edge_array<int>    cost3(G2);
  52.   edge_array<double> cost4(G2);
  53.  
  54.   node_array<int>  compnum1(U);
  55.  
  56.   cout << string("%6.2f sec\n",used_time(T));
  57.  
  58.  
  59.   edge e;
  60.  
  61.   cout << "assign edge labels   " << flush;
  62.   forall_edges(e,G1) cost2[e] = cost1[e] = G1[e] = random(0,1000);
  63.   forall_edges(e,G2) cost4[e] = cost3[e] = G2[e] = random(0,1000);
  64.   cout << string("%6.2f sec\n",used_time(T));
  65.  
  66.   newline;
  67.  
  68. /*
  69.   cout << "TOPSORT              " << flush;
  70.   TOPSORT(G1,ord); 
  71.   cout << string("%6.2f sec\n",used_time(T));
  72.  
  73.   cout << "DFS                  " << flush;
  74.   DFS(G1,s,reached);
  75.   cout << string("%6.2f sec\n",used_time(T));
  76.  
  77.   cout << "DFS_NUM              " << flush;
  78.   DFS_NUM(G1,dfs_num,comp_num);
  79.   cout << string("%6.2f sec\n",used_time(T));
  80.  
  81.   cout << "BFS                  " << flush;
  82.   BFS(G1,G1.first_node(),layer);
  83.   cout << string("%6.2f sec\n",used_time(T));
  84. */
  85.  
  86.   cout << "COMPONENTS           " << flush;
  87.   int c = COMPONENTS(U,compnum1);
  88.   cout << string("%6.2f sec  c = %d",used_time(T),c) << endl;
  89.  
  90.   cout << "COMPONENTS1          " << flush;
  91.   c = COMPONENTS1(U,compnum1);
  92.   cout << string("%6.2f sec  c = %d",used_time(T),c) << endl;
  93.  
  94.   cout << "STRONG_COMPONENTS    " << flush;
  95.   c = STRONG_COMPONENTS(G1,compnum);
  96.   cout << string("%6.2f sec  c = %d",used_time(T),c) << endl;
  97.  
  98.   cout << "SPANNING_TREE        " << flush;
  99.   list<edge> EL = SPANNING_TREE(G1);
  100.   cout << string("%6.2f sec |T| = %d",used_time(T),EL.length()) << endl;
  101.  
  102.   cout << "MS_TREE<int>         " << flush;
  103.   EL = MIN_SPANNING_TREE(G1,cost1);
  104.   c = 0;
  105.   forall(e,EL) c += cost1[e]; 
  106.   cout << string("%6.2f sec |T| = %d  W(T) = %d",used_time(T),EL.length(),c);
  107.   cout << endl;
  108.  
  109.   cout << "MS_TREE<double>      " << flush;
  110.   EL = MIN_SPANNING_TREE(G1,cost2);
  111.   double c2 = 0;
  112.   forall(e,EL) c2 += cost2[e]; 
  113.   cout << string("%6.2f sec |T| = %d  W(T) = %.2f",used_time(T),EL.length(),c2);
  114.   cout << endl;
  115.  
  116.   cout << "DIJKSTRA <int>       " << flush;
  117.   DIJKSTRA(G1,s,cost1,dist1,pred);
  118.   cout << string("%6.2f sec  d  = %d",used_time(T),dist1[t]) << endl;
  119.  
  120.   cout << "DIJKSTRA <double>    " << flush;
  121.   DIJKSTRA(G1,s,cost2,dist2,pred);
  122.   cout << string("%6.2f sec  d  = %.2f",used_time(T),dist2[t]) << endl;
  123.  
  124.   cout << "BELLMAN_FORD<int>    " << flush;
  125.   BELLMAN_FORD(G1,s,cost1,dist1,pred);
  126.   cout << string("%6.2f sec  d  = %d",used_time(T),dist1[t]) << endl;
  127.  
  128.   cout << "BELLMAN_FORD<double> " << flush;
  129.   BELLMAN_FORD(G1,s,cost2,dist2,pred);
  130.   cout << string("%6.2f sec  d  = %.2f",used_time(T),dist2[t]) << endl;
  131.  
  132.   if (G1.number_of_nodes() < 50)
  133.   { node_matrix<int> M(G1);
  134.     cout << "ALL PAIRS<int>       " << flush;
  135.     ALL_PAIRS_SHORTEST_PATHS(G1,cost1,M);
  136.     cout << string("%6.2f sec\n",used_time(T));
  137.    }
  138.  
  139.   cout << "MAX FLOW<int>        " << flush;
  140.   int f1 = MAX_FLOW(G1,s,t,cost1,flow1) ;
  141.   cout << string("%6.2f sec  f  = %d",used_time(T),f1) << endl;
  142.  
  143.   cout << "MAX FLOW<double>     " << flush;
  144.   double f2 = MAX_FLOW(G1,s,t,cost2,flow2) ;
  145.   cout << string("%6.2f sec  f  = %.2f",used_time(T),f2) << endl;
  146.  
  147.   cout << "MC  MATCHING         " << flush;
  148.   list<edge> M1 = MAX_CARD_MATCHING(G1);
  149.   cout << string("%6.2f sec |M| = %d",used_time(T),M1.length()) << endl;
  150.  
  151.   cout << "MCB MATCHING         " << flush;
  152.   list<edge> M2 = MAX_CARD_BIPARTITE_MATCHING(G2,A,B);
  153.   cout << string("%6.2f sec |M| = %d",used_time(T), M2.length()) << endl;
  154.   
  155.   cout << "MWB MATCHING<int>    " << flush;
  156.   list<edge> M3 = MAX_WEIGHT_BIPARTITE_MATCHING(G2,A,B,cost3);
  157.   int W1 = 0;
  158.   forall(e,M3) W1 += cost3[e];
  159.   cout << string("%6.2f sec |M| = %d  W(M) = %d",used_time(T), M3.length(),W1);
  160.   cout << endl;
  161.  
  162.   cout << "MWB MATCHING<double> " << flush;
  163.   list<edge> M4 = MAX_WEIGHT_BIPARTITE_MATCHING(G2,A,B,cost4);
  164.   double W2 = 0;
  165.   forall(e,M4) W2 += cost4[e];
  166.   cout << string("%6.2f sec |M| = %d  W(M) = %.2f",used_time(T),M4.length(),W2);
  167.   cout << endl;
  168.   
  169.   
  170.   if (G1.number_of_nodes() < 500)
  171.   { cout << "TRANSITIVE_CLOSURE   " << flush;
  172.     graph clos = TRANSITIVE_CLOSURE(G1);
  173.     cout << string("%6.2f sec |E| = %d",used_time(T),clos.number_of_edges()) << endl;
  174.   
  175.    }
  176.   
  177.   newline;
  178.   cout << "TOTAL TIME           ";
  179.   cout << string("%6.2f sec\n",used_time());
  180.  
  181.   return 0;
  182. }
  183.